package net.tp.algo.graph.shortestpath;

import net.tp.algo.graph.Graph;
import net.tp.algo.heap.BinaryHeap;

import java.util.*;

/**
 *
 *
 *
 */
public class Dijkstra {

    private final double[] distanceTo;
    private final int[] edgeTo;
    private final int source;

    public Dijkstra(Graph graph, int source) {

        this.source = source;

        int N = graph.order();

        this.distanceTo = new double[N];
        Arrays.fill(distanceTo, Double.MAX_VALUE);

        this.edgeTo = new int[N];
        Arrays.fill(edgeTo, -1);

        this.distanceTo[source] = 0;
        this.edgeTo[source] = source;

        BinaryHeap<Integer> heap = new BinaryHeap<>( (u, w) -> Double.compare(distanceTo[u], distanceTo(w)) );

        Set<Integer> settled = new HashSet<>();
        heap.add(source);
        while (!heap.empty()) {
            int u = heap.removeHead();
            settled.add(u);

            for (Graph.Edge edge : graph.edges(u)) {
                int w = edge.other(u);
                if (!settled.contains(w)) {
                    if (distanceTo[w] > distanceTo[u] + edge.weight()) {
                        distanceTo[w] = distanceTo[u] + edge.weight();
                        edgeTo[w] = u;
                        if (heap.contains(w)) heap.updatePriority(w);
                        else heap.add(w);
                    }
                }
            }
        }

    }

    public double distanceTo(int w) {
        return distanceTo[w];
    }

    public List<Integer> pathTo(int w) {
        List<Integer> result = new LinkedList<>();
        for (; w != source; w = edgeTo[w]) {
            result.add(0, w);
        }
        result.add(0, source);

        return result;
    }
}
